home *** CD-ROM | disk | FTP | other *** search
/ Hacker's Secrets 4 / Hacker's Secrets 4.iso / misc / mersenne.txt < prev    next >
Text File  |  1995-10-11  |  3KB  |  66 lines
  1. 3Q:  What are the values of:
  2.  
  3. largest known Mersenne prime?
  4.  
  5. A:  It is 2^859433-1. It was discovered by a Cray in 1994.
  6.     It has 258,716 digits.
  7.      1  2^859433-1                    258716 SG 94 Mersenne ?
  8.  
  9. What is the current status on Mersenne primes?
  10.  
  11. A:  Mersenne primes are primes of the form 2^p-1. For 2^p-1 to be prime 
  12.     we must have that p is prime. The following Mersenne primes are
  13.     known.
  14.  
  15.     nr            p                                 year  by
  16.     -----------------------------------------------------------------
  17.      1-5   2,3,5,7,13                    in or before the middle ages
  18.      6-7       17,19                     1588  Cataldi
  19.      8          31                       1750  Euler
  20.      9          61                       1883  Pervouchine
  21.     10          89                       1911  Powers
  22.     11          107                      1914  Powers
  23.     12          127                      1876  Lucas
  24.     13-14       521,607                  1952  Robinson
  25.     15-17       1279,2203,2281           1952  Lehmer
  26.     18          3217                     1957  Riesel
  27.     19-20       4253,4423                1961  Hurwitz & Selfridge
  28.     21-23       9689,9941,11213          1963  Gillies
  29.     24          19937                    1971  Tuckerman
  30.     25          21701                    1978  Noll & Nickel
  31.     26          23209                    1979  Noll
  32.     27          44497                    1979  Slowinski & Nelson
  33.     28          86243                    1982  Slowinski
  34.     29          110503                   1988  Colquitt & Welsh jr.
  35.     30          132049                   1983  Slowinski
  36.     31          216091                   1985  Slowinski
  37.     32?         756839                   1992  Slowinski & Gage
  38.     33?         859433                   1994  Slowinski & Gage
  39.  
  40.     The way to determine if 2^p-1 is prime is to use the Lucas-Lehmer 
  41.     test:
  42.       Lucas_Lehmer_Test(p):
  43.      u := 4
  44.      for i from 3 to p do
  45.         u := u^2-2 mod 2^p-1
  46.      od
  47.      if u == 0 then
  48.         2^p-1 is prime
  49.      else
  50.         2^p-1 is composite
  51.      fi
  52.  
  53.    The following ranges have been checked completely:
  54.     2 - 355K and  430K - 520K
  55.  
  56.    More on Mersenne primes and the Lucas-Lehmer test can be found in:
  57.       G.H. Hardy, E.M. Wright, An introduction to the theory of numbers,
  58.       fifth edition, 1979, pp. 16, 223-225.
  59.  
  60.  
  61. (Please send updates to alopez-o@maytag.UWaterloo.ca)
  62.  
  63. Alex Lopez-Ortiz                              alopez-o@maytag.UWaterloo.ca
  64. Department of Computer Science                      University of Waterloo
  65. Waterloo, Ontario                                                   Canada
  66.